/*
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v)  向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
CBTInserter.get_root() 将返回树的头节点。
 

示例 1：



输入
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
输出
[null, 1, 2, [1, 2, 3, 4]]

解释
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3);  // 返回 1
cBTInserter.insert(4);  // 返回 2
cBTInserter.get_root(); // 返回 [1, 2, 3, 4]
 

提示：

树中节点数量范围为 [1, 1000] 
0 <= Node.val <= 5000
root 是完全二叉树
0 <= val <= 5000 
每个测试用例最多调用 insert 和 get_root 操作 104 次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/complete-binary-tree-inserter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 队列
class CBTInserter {
private:
    TreeNode* m_root;
    queue<TreeNode*> m_q; // 里面放的是左右孩子节点有空的节点
public:
    CBTInserter(TreeNode* root) : m_root(root) {
        queue<TreeNode*> temp_q;
        temp_q.push(root);
        while (!temp_q.empty()) {
            TreeNode* node = temp_q.front();
            temp_q.pop();
            if (nullptr != node->left) {
                temp_q.push(node->left);
            }
            if (nullptr != node->right) {
                temp_q.push(node->right);
            }
            if (!(nullptr != node->left && nullptr != node->right)) {
                m_q.push(node);
            }
        }
    }

    int insert(int val) {
        TreeNode* node = m_q.front();
        TreeNode* child = new TreeNode(val);
        if (nullptr == node->left) {
            node->left = child;
        } else if (nullptr == node->right) {
            node->right = child;
            m_q.pop();
        }
        m_q.push(child);
        return node->val;
    }

    TreeNode* get_root() {
        return m_root;
    }
};

// 二进制表示
class CBTInserter {
public:
    CBTInserter(TreeNode* root) {
        this->root = root;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            ++cnt;
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    int insert(int val) {
        ++cnt;
        TreeNode* child = new TreeNode(val);
        TreeNode* node = root;
        int highbit = 31 - __builtin_clz(cnt); // __builtin_clz 返回前导0的个数
        for (int i = highbit - 1; i >= 1; --i) {
            if (cnt & (1 << i)) {
                node = node->right;
            }
            else {
                node = node->left;
            }
        }
        if (cnt & 1) {
            node->right = child;
        }
        else {
            node->left = child;
        }
        return node->val;
    }

    TreeNode* get_root() {
        return root;
    }

private:
    int cnt = 0; // 当前树中节点个数
    TreeNode* root;
};
